package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/subsets/
 * 子集
 *
 * 写得太慢了
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-28 16:15
 */
public class LeetCode78 {

    public static void main(String[] args) {
        LeetCode78 leetCode78 = new LeetCode78();
        List<List<Integer>> lists = leetCode78.subsets(new int[]{1, 2, 3, 4});
        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> path = new ArrayList<>();
        dfs(0,nums,path);
        return result;
    }

    public void dfs (int start,int[] nums,List<Integer> path) {
        if (start == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
//        for (int i = start;i < nums.length;i++) {
//            path.add(nums[start]);
//            dfs(start + 1,nums,path);
//            path.remove(path.size() - 1);
//        }
        dfs(start + 1,nums,path);
        path.add(nums[start]);
        dfs(start + 1,nums,path);
        path.remove(path.size() - 1);
    }

}
